// 2025/10/23
// 克隆图

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/

class Solution {
public:
    Node* cloneGraph(Node* node) {
        if(node == nullptr)
            return nullptr;
        unordered_map<Node*, Node*> old_new;
        queue<Node*> q;
        q.emplace(node);
        
        while(!q.empty())
        {
            Node* cur = q.front();
            q.pop();
            old_new.emplace(cur, new Node(cur->val));
            for(auto& neighbor : cur->neighbors)
            {
                if(old_new.count(neighbor) == 0)
                    q.emplace(neighbor);
            }
        }

        for(auto& pr : old_new)
        {
            for(auto& neighbor : pr.first->neighbors)
            {
                pr.second->neighbors.emplace_back(old_new[neighbor]);
            }
        }

        return old_new[node];
    }
};